\documentclass[13pt, compress]{beamer}

%\useoutertheme{infolines}
%\useoutertheme[footline=authortitle]{miniframes}

%\usetheme{Berlin}
\usetheme{Berkeley}
%\usetheme{Warsaw}
%\usetheme{Madrid}
%\usetheme{Singapore}
%\usetheme{Dresden}
%\usetheme{Ilmenau}
%\usetheme{Szeged}

\useinnertheme[shadow]{rounded}


%\useoutertheme{umbcfootline} 
%\setfootline{\insertshortinstitute, \insertshortdate 
%    \hfill slide \insertframenumber/\inserttotalframenumber} 


\usepackage{tikz}

\usepackage{polski}
\usepackage[T1]{fontenc}

\usepackage[polish]{babel}
\usepackage[utf8x]{inputenc}
\PrerenderUnicode{ą}
\PrerenderUnicode{ó}

\usecolortheme[rgb={0.3,0.2,0.5}]{structure}

\title[Zastosowanie programowania ewolucyjnego do rozwiązywania klasy problemów NP-zupełnych\hspace{2em}\insertframenumber/
\inserttotalframenumber]{Zastosowanie programowania ewolucyjnego do rozwiązywania klasy problemów NP-zupełnych}

%\author{Łukasz Szybka}
\author[Łukasz Szybka]{{\hugeŁukasz Szybka}\\ opiekun pracy:\\ dr inż. Mariusz Zubert}
\date{27 września 2010}
%\date{\today}
\institute[DMCS]


\begin{document}

%\onehalfspacing
\linespread{1.2}
%\baselineskip{16}
%\renewcommand\baselinestretch{1.5}

%TODO dodać slajd opisujący chromosom?



\frame
{
  \frametitle{\small POLITECHNIKA ŁÓDZKA\\ \vspace{-0.1cm}
  Wydział Elektrotechniki, Elektroniki, Informatyki i Automatyki\\ \vspace{-0.25cm}
  Kierunek: Informatyka}
  %\centering Praca dyplomowa magisterska
  \titlepage
}

\frame
{
  \frametitle{Plan prezentacji}%TODO agenda?
  \tableofcontents
}

\section[Wstęp]{Wstęp}

\frame
{
  \frametitle{Problemy NP-zupełne}
  \begin{itemize}
  \item Cechą problemów NP-zupełnych jest to, że nie jest znany algorytm szybkiego znajdowania rozwiązań
  \item Czas potrzebny na znalezienie rozwiązania problemu NP-zupełnego wzrasta bardzo szybko w miarę zwiększenia rozmiaru problemu
  \item Przykłady problemów NP-zupełnych:
    \begin{itemize}
    %\item Kolorowanie grafu
    \item Problem komiwojażera
    \item Problem plecakowy
    \item Tetris
    %\item Saper
    \item Sudoku
    \end{itemize}
  \end{itemize}
}

%\frame
%{
%  \frametitle{„Inteligentne” metody rozwiązywania problemów stosowane w informatyce}
%  \begin{itemize}
%  \item Sieci neuronowe
%  \item Algorytmy genetyczne
%  \item Logika rozmyta
%  \end{itemize}
%}

\section[Algorytmy genetyczne]{Algorytmy genetyczne}



\frame
{
  \frametitle{Algorytm genetyczny}
  \begin{itemize}
    \item Przeszukanie puli możliwych rozwiązań w celu znalezienia najlepszych
    \item Sposób poszukiwania rozwiązania naśladujący naturalny proces ewolucji
    \item Możliwe znalezienie rozwiązania w krótkim czasie nawet dla bardzo złożonych problemów
    \item Szybsze niż tradycyjne algorytmy w przypadku problemów NP-zupełnych
    \item Możliwe rozwiązania sub-optymalne
  \end{itemize}
}

\frame
{
  \frametitle{Założenia}
  \begin{itemize}
    \item Rozwiązania problemu kodujemy za pomocą chromosomów o określonej długości
    \item Definiujemy środowisko i jego parametry (prawdopodobieństwo mutacji, sposób oceny i wyboru najlepszych osobników)
    \item Definiujemy populację określonej wielkości
    \item Algorytm jest uniwersalny, niezależny od problemu który rozwiązuje
  \end{itemize}
}

\frame
{
  \frametitle{Funkcja oceny}
  \begin{itemize}
  \item Zadaniem funkcji oceny jest określenie które osobniki w populacji najlepiej spełniają warunki zadania
  \item Przyporządkowuje każdemu osobnikowi liczbową wartość która odpowiada jego przystosowaniu
  \item Oblicza dostosowanie całej populacji
  \item Jest jedynym elementem charakterystycznym dla konkretnego problemu
  \end{itemize}
}

%\frame
%{
%  \frametitle{Metody selekcji}
%  Na podstwie obliczonych wartości dostosowania osobników wybieramy te najlepsze
%  \begin{itemize}
%  \item Metoda ruletki
%  \item Metoda rankingowa
%  \item Metoda turniejowa
%  \end{itemize}
%}

\frame
{
  \frametitle{Krzyżowanie}
  \begin{itemize}
   \item Losowo wybrany punkt krzyżowania
   \item Możliwe różne warianty krzyżowania (np. wielopunktowe)
  \end{itemize}
  
%  \begin{center}
%      \begin{tabular}{ | l | l |}
%      \hline
%      Osobnik1 & \texttt {{\color{red}101}|{\color{red}101001}}\\ \hline
%      Osobnik2 & \texttt {{\color{blue}011}|{\color{blue}001101}}\\ \hline
%      potomek1 & \texttt {{\color{red}101}|{\color{blue}001101}}\\ \hline
%      potomek2 & \texttt {{\color{blue}011}|{\color{red}101001}}\\ \hline
%
%      \end{tabular}
%  \end{center}

\begin{table}[!ht]
  \begin{center}
  %\caption{Przykład krzyżowania jednopunktowego}
   \label{tb:crossover_example}
      \begin{tabular}{ | l | l | l|}
      \hline
      Reprezentacja & binarna & zmiennoprzecinkowa\\ \hline
      Osobnik 1 & \texttt {{\color{red}101}|{\color{red}101001}}& \texttt {{\color{red}11.34 12.54}|{\color{red}34.14}}\\ \hline
      Osobnik 2 & \texttt {{\color{blue}011}|{\color{blue}001101}}& \texttt {{\color{blue}31.43 11.51}|{\color{blue}11.51}}\\ \hline
      Potomek 1 & \texttt {{\color{red}101}|{\color{blue}001101}}& \texttt {{\color{red}11.34 12.54}|{\color{blue}11.51}}\\ \hline
      Potomek 2 & \texttt {{\color{blue}011}|{\color{red}101001}}& \texttt {{\color{blue}31.43 11.51}|{\color{red}34.14}}\\ \hline
      \end{tabular}
  \end{center}
\end{table}


}

\frame
{
  \frametitle{Mutacja}
  \begin{itemize}
   \item Dzięki mutacji unikamy przedwczesnej zbieżności do rozwiązań sub-optymalnych
   \item  Występują różne rodzaje mutacji
  \end{itemize}

%  \begin{center}
%      \begin{tabular}{ | l | l |}
%      \hline
%      przed mutacją & \texttt {101101001}\\ \hline
%      osobnik zmutowany & \texttt {101101{\color{red}1}01}\\ \hline
%      \end{tabular}
%  \end{center}

\begin{table}[!ht]
  \begin{center}
    %\caption{Przykład mutacji}
      \begin{tabular}{ | l | l | l|}
      \hline
      Reprezentacja & binarna & zmiennoprzecinkowa\\ \hline
      przed mutacją & \texttt {101101001} & \texttt {11.34 12.54 34.14}\\ \hline
      osobnik zmutowany & \texttt {101101{\color{red}1}01} &\texttt {11.34 {\color{red}41.22} 34.14}\\ \hline
      \end{tabular}
  \end{center}
\end{table}

}

\frame
{
  \frametitle{Warunek zakończenia}
  \begin{itemize}
  \item Osiągnięcie zadanej liczby generacji
  \item Brak poprawy w kilku ostatnich pokoleniach
  \item Znalezienie rozwiązania optymalnego (w przypadku problemów gdzie można to stwierdzić)
  \item Znalezienie rozwiązania bliskiego optymalnemu z zadaną dokładnością
  \end{itemize}

}

\frame
{
  \frametitle{Schemat blokowy algorytmu genetycznego}
	\begin{figure}
          \scalebox{0.4}
	  {
	    \input{../Schemat_blokowy_algorytmu_genetycznego}
	  }
	  %\centering
	  %\includegraphics[width=8cm]{Schemat_blokowy_algorytmu_genetycznego.jpeg}
	  %\input{Schemat_blokowy_algorytmu_genetycznego}
	  %\caption{Schemat blokowy algorytmu}
	  %\label{fig:block_diagram_algorithm}
	\end{figure}

  %\begin{overprint}
    
  %\end{overprint} 
}


\section[Moja praca]{Moja praca}

\frame
{
  \frametitle{Moja praca}
  \begin{itemize}
  \item Napisanie biblioteki wspomagającej obliczenia za pomocą algorytmów genetycznych
  \item Zastosowanie do rozwiązania kilku zagadnień
    \begin{itemize}
    \item Poszukiwanie maksimum funkcji w zadanym przedziale
    \item Problem komiwojażera
    \item Sudoku
    \end{itemize}
  \item Analiza najlepszych parametrów środowiska
  \item Analiza wyników, porównanie z innymi metodami poszukiwania rozwiązań
  \item Interfejs graficzny dla prezentacji rozwiązywania problemu komiwojażera
  \end{itemize}

}

\frame
{
  \frametitle{Problemy}
  \begin{itemize}
  \item Dobranie odpowiedniego kodowania informacji w chromosomie
  \item Dobranie parametrów środowiska
  \item Dobranie dodatkowych operatorów oprócz krzyżowania i mutacji w celu poprawy wyników
  \item Zaprojektowanie biblioteki umożliwiającej łatwe modyfikacje i dopasowanie do różnych zagadnień
  \end{itemize}
}

%\frame
%{
%  \frametitle{Wybrane technologie}
%  \begin{itemize}
%  \item C++
%  \item Biblioteka Qt 4.6
%  \item Dokumentacja kodu Doxygen
%  \end{itemize}
%}

%\frame
%{
%  \frametitle{Diagram klas}
%	\begin{figure}
%	  \centering
%	  \includegraphics[width=10cm]{../class_diagram}%[width=16cm, clip=true, trim=1cm 20cm 1cm 0cm]{../class_diagram}
%	  \caption{Diagram klas}
%	  \label{fig:class_diagram}
%	\end{figure}
%}

\section[Problem komiwojażera]{Problem komiwojażera}

\frame
{
  \frametitle{Opis problemu komiwojażera}
  \begin{itemize}
   \item Problem polega na znalezieniu najkrótszej drogi między podanymi miastami.
   \item Droga zaczyna się z ustalonego miasta i kończy w miejscu startu.
   \item Ilość możliwych dróg równa jest ilości permutacji podzielonej przez 2 (trasę można przebyć w dwóch kierunkach).
   \item Dla liczby miast n=20 ilość możliwych dróg wynosi $\frac{(n-1)!}{2}=\frac{19!}{2}=60822550204416000$
  \end{itemize}
}

\frame
{
  \frametitle{Reprezentacja w chromosomie}
  Chromosom zawierający ciąg liczb całkowitych od 0 do n-1. Liczby się nie powtarzają

  \begin{table}
    %\caption{Przykładowy chromosom dla problemu komiwojażera}
    %\label{tb:example_chromosome_salesman}
    \begin{center}
	\begin{tabular}{ | l | l |l |l |l |l |l |l |l |}
	\hline
	{\color{blue}1}&5&8&3&0&2&6&4&7\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=1]

\node at (1.38,1.08)
[circle,draw,name=p0,scale=0.7,thick] {0};
\node at (-1.05,1.58)
[circle,draw,name=p1,scale=0.7,thick, blue] {1};
\node at (1.52,-0.58)
[circle,draw,name=p2,scale=0.7,thick] {2};
\node at (2.52,1.33)
[circle,draw,name=p4,scale=0.7,thick] {4};
\node at (-2.11,0.33)
[circle,draw,name=p5,scale=0.7,thick] {5};
\node at (-1.03,-2.13)
[circle,draw,name=p3,scale=0.7,thick] {3};
\node at (3.03,-0.89)
[circle,draw,name=p6,scale=0.7,thick] {6};
\node at (1.44,-2.69)
[circle,draw,name=p7,scale=0.7,thick] {7};
\node at (-3.32,-1.59)
[circle,draw,name=p8,scale=0.7,thick] {8};

   \draw[->, very thick] (p1) -- (p5);
   \draw[->, very thick] (p5) -- (p8);
   \draw[->, very thick] (p8) -- (p3);
   \draw[->, very thick] (p3) -- (p0);
   \draw[->, very thick] (p0) -- (p2);
   \draw[->, very thick] (p2) -- (p6);
   \draw[->, very thick] (p6) -- (p4);
   \draw[->, very thick] (p4) -- (p7);
   \draw[->, very thick] (p7) -- (p1);


  \end{tikzpicture}
\end{figure}


}

\frame
{
  \frametitle{Krzyżowanie dla problemu komiwojażera}
  \begin{itemize}
   \item Zwykłe krzyżowanie prowadziłoby do utworzenia nieprawidłowych chromosomów.
   \item Należy zastosować wyspecjalizowane krzyżowanie które tworzy tylko prawidłowe chromosomy.
  \end{itemize}

  \begin{table}
    %\caption{Przykładowy chromosom dla problemu komiwojażera}
    %\label{tb:example_chromosome_salesman}
    \begin{center}
	\begin{tabular}{ | l | l | l|}
	\hline
	chromosom1 & chromosom2\\ \hline
	1 5 8 3 0|2 6 4 7 & 3 5 1 6 0|8 7 2 4\\ \hline
	1 5 {\color{red}2} 3 0|{\color{red}8} 6 4 7 & 3 5 1 6 0|{\color{red}2} 7 {\color{red}8} 4\\ \hline
	1 5 2 3 0|8 {\color{red}7} 4 {\color{red}6} & 3 5 1 {\color{red}7} 0|2 {\color{red}6} 8 4\\ \hline
	1 5 {\color{red}4} 3 0|8 7 {\color{red}2} 6 & 3 5 1 7 0|2 6 {\color{red}4} {\color{red}8}\\ \hline
	1 5 {\color{red}6} 3 0|8 7 2 {\color{red}4} & 3 5 1 {\color{red}8} 0|2 6 4 {\color{red}7}\\ \hline
	\end{tabular}
    \end{center}
  \end{table}


%\only<1>{1 5 2 3 7|6 4 0 8  \vline 3 5 1 8 7|2 6 4 0}
%\only<2>{1 5 2 3 7|{\color{red}6} 4 0 8   3 5 1 8 7|{\color{red}2} 6 4 0}
%\only<3>{1 5 2 3 7|6 {\color{red}4} 0 8   3 5 1 8 7|2 {\color{red}6} 4 0}
%\only<4>{1 5 2 3 7|6 4 {\color{red}0} 8   3 5 1 8 7|2 6 {\color{red}4} 0}
%\only<5>{1 5 2 3 7|6 4 0 {\color{red}8}   3 5 1 8 7|2 6 4 {\color{red}0}}


 % \begin{table}
    %\caption{Przykładowy chromosom dla problemu komiwojażera}
    %\label{tb:example_chromosome_salesman}
 %   \begin{center}
%	\begin{tabular}{ | l | l | l|}
%	\hline
%	chromosom1 & chromosom2\\ \hline %\noalign{\hrule height 2pt}
%\only<1>{1 5 2 3 7|6 4 0 8  & 3 5 1 8 7|2 6 4 0\\ \hline}
%\only<2>{1 5 2 3 7|{\color{red}6} 4 0 8  & 3 5 1 8 7|{\color{red}2} 6 4 0\\ \hline}
%\only<3>{1 5 2 3 7|6 {\color{red}4} 0 8  & 3 5 1 8 7|2 {\color{red}6} 4 0\\ \hline}
%\only<4>{1 5 2 3 7|6 4 {\color{red}0} 8  & 3 5 1 8 7|2 6 {\color{red}4} 0\\ \hline}
%\only<5>{1 5 2 3 7|6 4 0 {\color{red}8}  & 3 5 1 8 7|2 6 4 {\color{red}0}\\ \hline}

%\onslide<2->{1 5 2 3 7|6 4 0 8  & 3 5 1 8 7|2 6 4 0\\ \hline}
%	1 5 {\color{red}2} 3 0|{\color{red}8} 6 4 7 & 3 5 1 6 0|{\color{red}2} 7 {\color{red}8} 4\\ \hline
%	1 5 2 3 0|8 {\color{red}7} 4 {\color{red}6} & 3 5 1 {\color{red}7} 0|2 {\color{red}6} 8 4\\ \hline
%	1 5 {\color{red}4} 3 0|8 7 {\color{red}2} 6 & 3 5 1 7 0|2 6 {\color{red}4} {\color{red}8}\\ \hline
%	1 5 {\color{red}6} 3 0|8 7 2 {\color{red}4} & 3 5 1 {\color{red}8} 0|2 6 4 {\color{red}7}\\ \hline
%	\end{tabular}
 %   \end{center}
 % \end{table}


%15237|6408   35187|2640
%15837|2640   35127|6408

}

\frame
{
  \frametitle{Przykład krzyżowania}

%15237|6408   35187|2640
%15837|2640   35127|6408

\begin{columns}[T] % the "c" option specifies center vertical alignment
\column{.45\textwidth}
chromosom1
  \begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.6]

  \node at (1.38,1.08)
  [circle,draw,name=p0,scale=0.7,thick] {0};
  \node at (-1.05,1.58)
  [circle,draw,name=p1,scale=0.7,thick] {1};
  \node at (1.52,-0.58)
  [circle,draw,name=p2,scale=0.7,thick] {2};
  \node at (2.52,1.33)
  [circle,draw,name=p4,scale=0.7,thick] {4};
  \node at (-2.51,0.33)
  [circle,draw,name=p5,scale=0.7,thick] {5};
  \node at (-1.03,-2.13)
  [circle,draw,name=p3,scale=0.7,thick] {3};
  \node at (3.03,-0.89)
  [circle,draw,name=p6,scale=0.7,thick] {6};
  \node at (1.44,-2.69)
  [circle,draw,name=p7,scale=0.7,thick] {7};
  \node at (-3.32,-1.59)
  [circle,draw,name=p8,scale=0.7,thick] {8};

    %\draw[->, very thick] (p1) -- (p5);
    %\draw[->, very thick] (p5) -- (p8);
    %\draw[->, very thick] (p8) -- (p3);
    %\draw[->, very thick] (p3) -- (p0);
    %\draw[->, very thick] (p0) -- (p2);
    %\draw[->, very thick] (p2) -- (p6);
    %\draw[->, very thick] (p6) -- (p4);
    %\draw[->, very thick] (p4) -- (p7);
    %\draw[->, very thick] (p7) -- (p1);

%15237|6408
    \draw[->, very thick] (p1) -- (p5);
    \draw[->, very thick] (p5) -- (p2);
    \draw[->, very thick] (p2) -- (p3);
    \draw[->, very thick] (p3) -- (p7);
    \draw[->, very thick] (p7) -- (p6);
    \draw[->, very thick] (p6) -- (p4);
    \draw[->, very thick] (p4) -- (p0);
    \draw[->, very thick] (p0) -- (p8);
    \draw[->, very thick] (p8) -- (p1);


%\draw
%(current bounding box.south west) rectangle
%(current bounding box.north east);


    \end{tikzpicture}
  \end{figure}
\onslide<2>
{
  \vspace*{-0.5cm}
  potomek1
  \vspace*{-0.5cm}
    \begin{figure}
      \centering
      \begin{tikzpicture}[scale=0.6]

    \node at (1.38,1.08)
    [circle,draw,name=p0,scale=0.7,thick] {0};
    \node at (-1.05,1.58)
    [circle,draw,name=p1,scale=0.7,thick] {1};
    \node at (1.52,-0.58)
    [circle,draw,name=p2,scale=0.7,thick] {2};
    \node at (2.52,1.33)
    [circle,draw,name=p4,scale=0.7,thick] {4};
    \node at (-2.51,0.33)
    [circle,draw,name=p5,scale=0.7,thick] {5};
    \node at (-1.03,-2.13)
    [circle,draw,name=p3,scale=0.7,thick] {3};
    \node at (3.03,-0.89)
    [circle,draw,name=p6,scale=0.7,thick] {6};
    \node at (1.44,-2.69)
    [circle,draw,name=p7,scale=0.7,thick] {7};
    \node at (-3.32,-1.59)
    [circle,draw,name=p8,scale=0.7,thick] {8};

  %15837|2640
      \draw[->, very thick] (p1) -- (p5);
      \draw[->, very thick] (p5) -- (p8);
      \draw[->, very thick] (p8) -- (p3);
      \draw[->, very thick] (p3) -- (p7);
      \draw[->, very thick] (p7) -- (p2);
      \draw[->, very thick] (p2) -- (p6);
      \draw[->, very thick] (p6) -- (p4);
      \draw[->, very thick] (p4) -- (p0);
      \draw[->, very thick] (p0) -- (p1);

  %\draw
  %(current bounding box.south west) rectangle
  %(current bounding box.north east);

      \end{tikzpicture}
    \end{figure}
  \column{.1\textwidth}
  \begin{figure}
  \centering
    \vspace*{1cm}
    \begin{tikzpicture}[scale=4]
      \draw [->,double,thick](-0.1,-2) -- (0.1,-3);
      \draw [->,double,thick](0.1,-2) -- (-0.1,-3);
    \end{tikzpicture}
  \end{figure}
}


\column{.45\textwidth} % column designated by a command
%15837|2640   35127|6408
%15237|6408   35187|2640
chromosom2
  \begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.6]

  \node at (1.38,1.08)
  [circle,draw,name=p0,scale=0.7,thick] {0};
  \node at (-1.05,1.58)
  [circle,draw,name=p1,scale=0.7,thick] {1};
  \node at (1.52,-0.58)
  [circle,draw,name=p2,scale=0.7,thick] {2};
  \node at (2.52,1.33)
  [circle,draw,name=p4,scale=0.7,thick] {4};
  \node at (-2.51,0.33)
  [circle,draw,name=p5,scale=0.7,thick] {5};
  \node at (-1.03,-2.13)
  [circle,draw,name=p3,scale=0.7,thick] {3};
  \node at (3.03,-0.89)
  [circle,draw,name=p6,scale=0.7,thick] {6};
  \node at (1.44,-2.69)
  [circle,draw,name=p7,scale=0.7,thick] {7};
  \node at (-3.32,-1.59)
  [circle,draw,name=p8,scale=0.7,thick] {8};

    %\draw[->, very thick] (p1) -- (p2);
    %\draw[->, very thick] (p2) -- (p7);
    %\draw[->, very thick] (p7) -- (p6);
    %\draw[->, very thick] (p6) -- (p4);
    %\draw[->, very thick] (p4) -- (p0);
    %\draw[->, very thick] (p0) -- (p8);
    %\draw[->, very thick] (p8) -- (p3);
    %\draw[->, very thick] (p3) -- (p5);
    %\draw[->, very thick] (p5) -- (p1);

%35187|2640
    \draw[->, very thick] (p3) -- (p5);
    \draw[->, very thick] (p5) -- (p1);
    \draw[->, very thick] (p1) -- (p8);
    \draw[->, very thick] (p8) -- (p7);
    \draw[->, very thick] (p7) -- (p2);
    \draw[->, very thick] (p2) -- (p6);
    \draw[->, very thick] (p6) -- (p4);
    \draw[->, very thick] (p4) -- (p0);
    \draw[->, very thick] (p0) -- (p3);

%\draw [->,double,thick](0,-3) -- (0,-4);

%\draw
%(current bounding box.south west) rectangle
%(current bounding box.north east);



    \end{tikzpicture}
  \end{figure}
\onslide<2>
{
  \vspace*{-0.5cm}
  potomek2
  \vspace*{-0.5cm}

    \begin{figure}
      \centering
      \begin{tikzpicture}[scale=0.6]

    \node at (1.38,1.08)
    [circle,draw,name=p0,scale=0.7,thick] {0};
    \node at (-1.05,1.58)
    [circle,draw,name=p1,scale=0.7,thick] {1};
    \node at (1.52,-0.58)
    [circle,draw,name=p2,scale=0.7,thick] {2};
    \node at (2.52,1.33)
    [circle,draw,name=p4,scale=0.7,thick] {4};
    \node at (-2.51,0.33)
    [circle,draw,name=p5,scale=0.7,thick] {5};
    \node at (-1.03,-2.13)
    [circle,draw,name=p3,scale=0.7,thick] {3};
    \node at (3.03,-0.89)
    [circle,draw,name=p6,scale=0.7,thick] {6};
    \node at (1.44,-2.69)
    [circle,draw,name=p7,scale=0.7,thick] {7};
    \node at (-3.32,-1.59)
    [circle,draw,name=p8,scale=0.7,thick] {8};

      %\draw[->, very thick] (p1) -- (p5);
      %\draw[->, very thick] (p5) -- (p8);
      %\draw[->, very thick] (p8) -- (p3);
      %\draw[->, very thick] (p3) -- (p0);
      %\draw[->, very thick] (p0) -- (p2);
      %\draw[->, very thick] (p2) -- (p6);
      %\draw[->, very thick] (p6) -- (p4);
      %\draw[->, very thick] (p4) -- (p7);
      %\draw[->, very thick] (p7) -- (p1);

    %35127|6408
      \draw[->, very thick] (p3) -- (p5);
      \draw[->, very thick] (p5) -- (p1);
      \draw[->, very thick] (p1) -- (p2);
      \draw[->, very thick] (p2) -- (p7);
      \draw[->, very thick] (p7) -- (p6);
      \draw[->, very thick] (p6) -- (p4);
      \draw[->, very thick] (p4) -- (p0);
      \draw[->, very thick] (p0) -- (p8);
      \draw[->, very thick] (p8) -- (p3);

  %\draw
  %(current bounding box.south west) rectangle
  %(current bounding box.north east);

      \end{tikzpicture}
    \end{figure}
}
\end{columns}




}


\frame
{
  \frametitle{Mutacja dla problemu komiwojażera}
  Mutacja zamienia miejscami kolejność odwiedzenia dwóch losowych miast.

  \begin{table}
    \begin{center}
	\begin{tabular}{|l | l | l |l |l |l |l |l |l |l |}
	\hline
	przed mutacją &1&5&8&3&0&2&6&4&7\\ \hline
	po mutacji    &1&5&8&3&{\color{red}7}&2&6&4&{\color{red}0}\\ \hline
	%po mutacji    &1&5&{\color{red}2}&3&0&{\color{red}8}&6&4&7\\ \hline
	\end{tabular}
    \end{center}
  \end{table}

\begin{figure}
  \centering
  \begin{tikzpicture}[scale=1]

\node at (1.38,1.08)
[circle,draw,name=p0,scale=0.7,thick, red] {0};

\node at (-1.05,1.58)
[circle,draw,name=p1,scale=0.7,thick] {1};

\node at (1.52,-0.58)
[circle,draw,name=p2,scale=0.7,thick] {2};

\node at (2.52,1.33)
[circle,draw,name=p4,scale=0.7,thick] {4};

\node at (-2.11,0.33)
[circle,draw,name=p5,scale=0.7,thick] {5};

\node at (-1.03,-2.13)
[circle,draw,name=p3,scale=0.7,thick] {3};

\node at (3.03,-0.89)
[circle,draw,name=p6,scale=0.7,thick] {6};

\node at (1.44,-2.69)
[circle,draw,name=p7,scale=0.7,thick, red] {7};

\node at (-3.32,-1.59)
[circle,draw,name=p8,scale=0.7,thick] {8};

   \draw[->, very thick] (p1) -- (p5);
   \draw[->, very thick] (p5) -- (p8);
   \draw[->, very thick] (p8) -- (p3);


\onslide<1>
{
   \draw[->, very thick] (p3) -- (p0);
   \draw[->, very thick] (p0) -- (p2);
}

\onslide<2>
{
   \draw[->, thick, dotted] (p3) -- (p0);
   \draw[->, thick, dotted] (p0) -- (p2);
}

   \draw[->, very thick] (p2) -- (p6);
   \draw[->, very thick] (p6) -- (p4);

\onslide<1>
{
   \draw[->, very thick] (p4) -- (p7);
   \draw[->, very thick] (p7) -- (p1);
}

\onslide<2>
{
   \draw[->, thick, dotted] (p4) -- (p7);
   \draw[->, thick, dotted] (p7) -- (p1);
}

\onslide<2>
{
   \draw[->, very thick, red] (p3) -- (p7);
   \draw[->, very thick, red] (p7) -- (p2);

   \draw[->, very thick, red] (p4) -- (p0);
   \draw[->, very thick, red] (p0) -- (p1);
}


  \end{tikzpicture}
\end{figure}


}

\frame
{
  \frametitle{Przykład 16 miast}


\begin{columns}[T] % the "c" option specifies center vertical alignment
\column{.5\textwidth}
\begin{itemize}
 \item Algorytm uruchomiono 100 razy
 \item Średnio algorytm sprawdzał 4203 dróg
 \item czyli $0.000000323\%$ %$\frac{4203}{1307674368000}\cdot100\% = 0.000000323\%$
 \item Algorytm był zbieżny
 \item Znaleziono rozwiązanie optymalne
\end{itemize}


\column{.5\textwidth}
  \begin{figure}[h]
  \begin{tikzpicture}[scale=0.5]
  \fill(0,2) circle (3pt);
  \fill(0,3) circle (3pt);
  \fill(0,4) circle (3pt);
  \fill(1,5) circle (3pt);
  \fill(2,6) circle (3pt);
  \fill(3,6) circle (3pt);
  \fill(4,6) circle (3pt);
  \fill(5,5) circle (3pt);
  \fill(6,4) circle (3pt);
  \fill(6,3) circle (3pt);
  \fill(6,2) circle (3pt);
  \fill(5,1) circle (3pt);
  \fill(4,0) circle (3pt);
  \fill(3,0) circle (3pt);
  \fill(2,0) circle (3pt);
  \fill(1,1) circle (3pt);

    \draw[step=1] (0,0) grid (6,6);

   \draw[thick, red] (0,4) -- (0,2) -- (2,0) -- (4,0) --  (6,2) -- (6,4) -- (4,6) -- (2,6) -- (0,4);

  \end{tikzpicture}
  \end{figure}
\small
\begin{block}
 {Najkrótsza droga}
  $8 + 8\sqrt{8} \approx 19.313708$
\end{block}

\begin{block}
 {Liczba możliwych dróg}
  $\frac{(n-1)!}{2}=\frac{15!}{2}=1307674368000$
\end{block}

\end{columns}
}

\frame
{
  \frametitle{Podsumowanie i wnioski}
  \begin{itemize}
   \item Pozornie losowy algorytm genetyczny można wykorzystać do rozwiązywania problemów NP-zupełnych
   \item Możliwe jest napisanie uniwersalnej biblioteki obliczeń ewolucyjnych
   \item Istotnym etapem projektowania algorytmu genetycznego jest dobór parametrów środowiska
   \item Algorytmy genetyczne osiągają dobre wyniki w połączeniu z metodami deterministycznymi
  \end{itemize}
}

\end{document}


